要解决的问题

已知Ax = b求解x

求解思路

设A = LU，通过LU分解，可以通过已知的A分解出确定的L阵和U阵（具体分解方法见下一节）。
那么我们得到LUx = b，即

在（1）中，L阵由LU分解得到，b已知，所以可以解出y。
在（2）中，U阵由LU分解得到，y已知，所以解出x也是手拿把掐。

如何通过LU分解得到L阵和U阵

最简单的方法是高斯消元法：

易于理解的是$L_2{L}_1{L}_0=L^{-1}$，消元的结果就是U。
算法：

因为有三重嵌套的循环，所有LU分解的复杂度是 𝑂(𝑛3) ，其中 加法操作∼$\frac{1}{3}{𝑛}^3$，乘法操作 ∼$\frac{1}{3}{𝑛}^3$，一共∼$\frac{2}{3}{𝑛}^3$。
总体来看，使用LU分解求解线性系统的计算量：

• 第一步：LU分解：∼$\frac{2}{3}{𝑛}^3$ （计算量最大的部分）
• 第二步：求解 𝐿𝑦=𝑏： ∼${𝑛}^2$
• 第三步：求解 𝑈𝑥=𝑦： ∼${𝑛}^2$